Ông tên thật là Nguyễn Hữu Vũ, sinh ngày 1 tháng 3 năm 1923, tại làng Trung Thôn, xã Quảng Trung, phủ Quảng Trạch, Quảng Bình, xuất thân trong một gia đình trung lưu. Song thân ông là ông Nguyễn Hữu Khoán và bà Đặng Thị Cấp, đều là những hậu duệ của thủ lĩnh Phong trào Cần Vương. Ông là con thứ 5 trong gia đình. Cha ông mất sớm khi ông mới 10 tuổi.

Thuở nhỏ, ông được cha dạy chữ Hán và theo học chữ Quốc ngữ bậc tiểu học tại Thọ Linh (nay thuộc xã Quảng Sơn, huyện Quảng Trạch). Chịu ảnh hưởng của gia đình, ông sớm đã có tinh thần chống thực dân Pháp. Năm 12 tuổi, ông bắt đầu tham gia hoạt động cách mạng dưới sự hướng dẫn của ông Nguyễn Văn Huyên (bí danh là Tế), một cán bộ của Đảng Cộng sản Đông Dương. Năm 1938, ông gia nhập Đảng Cộng sản Đông Dương, lấy bí danh là Nguyễn Văn Đồng.[2]

Năm 1940, ông được cử làm Bí thư chi bộ Trung Thôn (mật danh là chi bộ Bình). Cùng năm này, ông theo học bậc trung học tại trường Saint Marie ở thị xã Đồng Hới. Một năm sau, ông được phân công làm Bí thư chi bộ tại trường. Những hoạt động của ông sớm bị chính quyền thực dân theo dõi. Vì vậy, khi đang học năm thứ 3 bậc Thành chung, ông bị thực dân Pháp truy nã và phải chuyển vào bí mật tại Lào và Thái Lan, hoạt động trong phong trào Việt kiều yêu nước để gây dựng cơ sở.

Năm 1944, ông bí mật trở về Việt Nam hoạt động, phụ trách Phủ ủy Quảng Trạch, làm chủ nhiệm báo Hồng Lạc và xây dựng chiến khu Trung Thuần, huấn luyện quân sự, tham gia Cách mạng tháng 8. Sau Cách mạng tháng 8, ông được bầu làm Chủ nhiệm Việt Minh, kiêm chỉ huy trưởng bộ đội Quảng Bình. Năm 1946, ông trúng cử đại biểu Quốc hội khóa I.